package org.example.myleet.rosalind.lcsq;

import org.example.myleet.rosalind.utils.FastaReader;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
//        solution.findLongestCommonSubsequence("AACCTTGG", "ACACTGTGA");
        solution.findLongestCommonSubsequence(FastaReader.parseFastaInput(">Rosalind_8974\n" +
                "CGTCGCAATCGGATAACGTCATTCTGGGCCAAATGTATTATCGTACGCCGCCCTACGAAA\n" +
                "CAGTCCCCAGGGGTGGGCGACGGAATCCGCCGCCCGAGGAGCTCCTATATCTAAAACTAG\n" +
                "ACTTTAGAGGCTTACAAATCAGAAGGGGGCAAGCGACGTTTCCGGGCGGGCCTCGATGAA\n" +
                "GAATGCGTGTGAGTGCGTCACTACCATCTGCAAATGTCGCTCATGTAGGTGGACTACGCT\n" +
                "ACTGCGATGCGCAACCGTTTAAACCTGAGACGAATAAGATTGTCTAAGGAATTCAACTAT\n" +
                "CCTATGAACCGCATGTATGTTTTGCGCCACGTGTTATGACACTATATGGTAATAGGCCGA\n" +
                "GAGTGAGGGTCAGATCCCTAGCATCAAGGCTACGTGTGCATGTAGCGCCGGCGCCAACTC\n" +
                "CTTCACATGATCAGACGATAGCGCCTCGTAGCGCTGGCGGGTAGCGACTCATTGGATAGG\n" +
                "CTTCCCGCCTACTAATGAAACCCTTATCACGATTGCGAGCTTTCCTCGACGCTCTATCAG\n" +
                "GTGCACTATAAGAGGTCGCACTTCAAAAGGCTGTTCTTGACCCCGGTCGTTGGCCTAACC\n" +
                "AGGCACGCTGCGGCATAAGCATTTAGTTCCGTCTTAGGACTCTGCAATGGTCATCTTATT\n" +
                "TTCCACGTCCTCCCCGCATCGTTCTGAGATCAATTACCGTGCGGAATGGACAGAACAAAC\n" +
                "CGCTGGCGTTACGACATGATCCGGTTAGGGCCCGTTTGGCCATAATTTGTGACACTTATC\n" +
                "ATCGTAAGATAGTCTAATTGGTTTGCTTCGGTCGGCATATCCTGCTATAGGCAAGCACTG\n" +
                "ACGGGACAGAAGTTGATACGACGTACTTCG\n").get(0).getSequence(), FastaReader.parseFastaInput(">Rosalind_9261\n" +
                "TTAAGAAACCCCTGATTTCTACCGGTGGGAAGTTGGATTATCCCTTTCACAGGGACCCAA\n" +
                "GACCTCTATACTGCCCGCGTATGTTTGTCCTCTCAACCCTCTTGACTGGCAGCTAGAAAG\n" +
                "GCCAGCTAACGGCTGTAGCGCAAATTTAGACCTCGAGGCTGTGGGTTAGACCACTATGAA\n" +
                "CTTGGGCATTGACTTACTTGAAAGCCCGCTTTCTTTTAGACGATGTCAGGCCCGTTAGCG\n" +
                "ATATAGTAACTACCCGCCCTGTATATGCATCAGTTTGACTTGGAGCCTCTTTAGGATCCG\n" +
                "ATAGCCCTGATCTTAGGTAGGTCTTTGCCTTTGAAAAAGGCGCTTTATAACACTGCTAGG\n" +
                "CTCTGTGGACGTGCATGTCCCATAGCTAGCCTTCGTACCCAGTGTCAGCTGAGGCTGCGG\n" +
                "GCAAGTACTCTAGCATAATCAGAAGCTAAAGTGCCCTCCCCATCAATATACATTCCAACA\n" +
                "CGGCGACTGGATAATGTATGGCACGCGCTGCTAGCAGTTTCATAGCCATGGCTGTGGTGT\n" +
                "GGGAGGTAACACAAAGTTATCGTTACCTAAGTACTGTGTCAACATCTAGCAGCCTATTCG\n" +
                "GTCTAATGACTCACATTGGCTAGATGCGCTAGCGTCCACTGTGAACTCGTGTCGGGTTAG\n" +
                "GTAAAGTCTAGCCCCTTCTTAGGCGTGCGTAGACCCTCCGGCACCCTCAATCATCGATAT\n" +
                "GGACATCCACACCGATTCGATCACCCTGTATAACTAAACAGCCGGTTGTATTTGTTCGAG\n" +
                "AAATGAGCAACAAACAGTGAACGACGTGATACCGCAATTAAGTATTATTTCCTATTTGTG\n" +
                "TTGCCTGTAAGTCTTTTGGAACAGACTGACGGATTAGATCTACCC\n").get(0).getSequence());
    }

    public void findLongestCommonSubsequence(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        dp[0][0] = 0;
        for (int i = 0; i < s.length(); ++i) {
            dp[i][0] = 0;
        }
        for (int j = 0; j < t.length(); ++j) {
            dp[0][j] = 0;
        }
        for (int i = 0; i < s.length(); ++i) {
            for (int j = 0; j < t.length(); ++j) {
                dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
                int elongation = s.charAt(i) == t.charAt(j) ? 1 : 0;
                dp[i + 1][j + 1] = Math.max(dp[i + 1][j + 1], dp[i][j] + elongation);
            }
        }
        StringBuilder res = new StringBuilder();
        int i = s.length(), j = t.length();
        while (i > 0 && j > 0) {
            if (dp[i][j] > dp[i - 1][j - 1] && dp[i][j] > dp[i - 1][j] && dp[i][j] > dp[i][j - 1]) {
                --i;
                --j;
                res.append(s.charAt(i));
            } else if (dp[i - 1][j] >= dp[i][j - 1]) {
                --i;
            } else {
                --j;
            }
        }
        res.reverse();
        System.out.println(res);
    }
}
